home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 16 / CU Amiga Magazine's Super CD-ROM 16 (1997-10-16)(EMAP Images)(GB)[!][issue 1997-11].iso / CUCD / Graphics / Ghostscript / source / istack.c < prev    next >
C/C++ Source or Header  |  1997-06-29  |  16KB  |  501 lines
  1. /* Copyright (C) 1992, 1995, 1996 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* istack.c */
  20. /* Ghostscript expandable stack manager */
  21. #include "memory_.h"
  22. #include "ghost.h"
  23. #include "gsstruct.h"
  24. #include "gsutil.h"
  25. #include "errors.h"
  26. #include "ialloc.h"
  27. #include "istack.h"
  28. #include "istruct.h"        /* for gs_reloc_refs */
  29. #include "iutil.h"
  30. #include "ivmspace.h"        /* for local/global test */
  31. #include "store.h"
  32.  
  33. /* Forward references */
  34. private void init_block(P3(ref_stack *, ref *, uint));
  35. int ref_stack_push_block(P3(ref_stack *, uint, uint));
  36.  
  37. /* GC procedures */
  38. #define sptr ((ref_stack *)vptr)
  39. private CLEAR_MARKS_PROC(ref_stack_clear_marks) {
  40.     r_clear_attrs(&sptr->current, l_mark);
  41. }
  42. private ENUM_PTRS_BEGIN(ref_stack_enum_ptrs) return 0;
  43.     case 0:
  44.         *pep = &sptr->current;
  45.         return ptr_ref_type;
  46. ENUM_PTRS_END
  47. private RELOC_PTRS_BEGIN(ref_stack_reloc_ptrs) {
  48. #if stacks_are_segmented
  49.     /* In a segmented environment, the top block can't move, */
  50.     /* so we don't need to relocate pointers to it. */
  51. #else
  52.     /* Note that the relocation must be a multiple of sizeof(ref_packed) */
  53.     /* * align_packed_per_ref, but it need not be a multiple of */
  54.     /* sizeof(ref).  Therefore, we must do the adjustments using */
  55.     /* ref_packed pointers rather than ref pointers. */
  56.     ref_packed *bot = (ref_packed *)sptr->current.value.refs;
  57.     long reloc;
  58.     gs_reloc_refs((ref_packed *)&sptr->current,
  59.               (ref_packed *)(&sptr->current + 1),
  60.               gcst);
  61.     r_clear_attrs(&sptr->current, l_mark);
  62.     reloc = bot - (ref_packed *)sptr->current.value.refs;
  63. #define reloc_p(p)\
  64.   sptr->p = (ref *)((ref_packed *)sptr->p - reloc);
  65.     reloc_p(p);
  66.     reloc_p(bot);
  67.     reloc_p(top);
  68. #undef reloc_p
  69. #endif
  70. } RELOC_PTRS_END
  71. /* Structure type for a ref_stack. */
  72. public_st_ref_stack();
  73.  
  74. /* Initialize a stack. */
  75. void
  76. ref_stack_init(register ref_stack *pstack, ref *psb,
  77.   uint bot_guard, uint top_guard, ref *pguard, gs_ref_memory_t *mem)
  78. {    uint size = r_size(psb);
  79.     uint avail = size - (stack_block_refs + bot_guard + top_guard);
  80.     ref_stack_block *pblock = (ref_stack_block *)psb->value.refs;
  81.     s_ptr body = (s_ptr)(pblock + 1);
  82.     pstack->bot = body + bot_guard;
  83.     pstack->p = pstack->bot - 1;
  84.     pstack->top = pstack->p + avail;
  85.     pstack->current = *psb;
  86.     pstack->extension_size = 0;
  87.     pstack->extension_used = 0;
  88.  
  89.     make_int(&pstack->max_stack, avail);
  90.     pstack->requested = 0;
  91.  
  92.     pstack->bot_guard = bot_guard;
  93.     pstack->top_guard = top_guard;
  94.     pstack->block_size = size - segmented_guard(bot_guard + top_guard);
  95.     pstack->body_size = avail;
  96.     if ( pguard != 0 )
  97.       pstack->guard_value = *pguard;
  98.     else
  99.       make_tav(&pstack->guard_value, t__invalid, 0, intval, 0);
  100.     pstack->underflow_error = -1;        /* bogus, caller must set */
  101.     pstack->overflow_error = -1;        /* bogus, caller must set */
  102.     pstack->allow_expansion = true;        /* default, caller may reset */
  103.     pstack->memory = mem;
  104.     init_block(pstack, psb, 0);
  105.     refset_null(pstack->bot, avail);
  106.     make_empty_array(&pblock->next, 0);
  107. }
  108.  
  109. /* Set the maximum number of elements allowed on a stack. */
  110. int
  111. ref_stack_set_max_count(ref_stack *pstack, long nmax)
  112. {    uint nmin = pstack->extension_size + (pstack->top - pstack->bot + 1);
  113.     if ( nmax < nmin )
  114.       nmax = nmin;
  115.     if ( nmax > max_uint / sizeof(ref) )
  116.       nmax = max_uint / sizeof(ref);
  117.     if ( !pstack->allow_expansion )
  118.       {    uint ncur = pstack->body_size;
  119.         if ( nmax > ncur )
  120.           nmax = ncur;
  121.       }
  122.     pstack->max_stack.value.intval = nmax;
  123.     return 0;
  124. }
  125.  
  126. /* Return the number of elements on a stack. */
  127. uint
  128. ref_stack_count(const ref_stack *pstack)
  129. {    return pstack->extension_used + (pstack->p - pstack->bot + 1);
  130. }
  131.  
  132. /* Retrieve a given element from the stack, counting from */
  133. /* 0 as the top element. */
  134. ref *
  135. ref_stack_index(const ref_stack *pstack, long idx)
  136. {    ref_stack_block *pblock;
  137.     uint used = pstack->p + 1 - pstack->bot;
  138.     if ( idx < 0 )
  139.         return NULL;
  140.     if ( idx < used )        /* common case */
  141.         return pstack->p - (uint)idx;
  142.     pblock = (ref_stack_block *)pstack->current.value.refs;
  143.     do
  144.     {    pblock = (ref_stack_block *)pblock->next.value.refs;
  145.         if ( pblock == 0 )
  146.             return NULL;
  147.         idx -= used;
  148.         used = r_size(&pblock->used);
  149.     }
  150.     while ( idx >= used );
  151.     return pblock->used.value.refs + (used - 1 - (uint)idx);
  152. }
  153.  
  154. /* Count the number of elements down to and including the first mark. */
  155. /* If no mark is found, return 0. */
  156. uint
  157. ref_stack_counttomark(const ref_stack *pstack)
  158. {    uint scanned = 0;
  159.     STACK_LOOP_BEGIN(pstack, p, used)
  160.     {    uint count = used;
  161.         p += used - 1;
  162.         for ( ; count; count--, p-- )
  163.           if ( r_has_type(p, t_mark) )
  164.             return scanned + (used - count + 1);
  165.         scanned += used;
  166.     }
  167.     STACK_LOOP_END(p, used)
  168.     return 0;
  169. }
  170.  
  171. /* Do the store check for storing elements of a stack into an array. */
  172. /* May return e_invalidaccess. */
  173. int
  174. ref_stack_store_check(const ref_stack *pstack, ref *parray, uint count,
  175.   uint skip)
  176. {    uint space = r_space(parray);
  177.  
  178.     if ( space != avm_local )
  179.       {    uint left = count, pass = skip;
  180.  
  181.         STACK_LOOP_BEGIN(pstack, ptr, size)
  182.           if ( size <= pass )
  183.             pass -= size;
  184.           else
  185.             {    int code;
  186.             if ( pass != 0 )
  187.               size -= pass, pass = 0;
  188.             ptr += size;
  189.             if ( size > left )
  190.               size = left;
  191.             left -= size;
  192.             code = refs_check_space(ptr - size, size, space);
  193.             if ( code < 0 )
  194.               return code;
  195.             if ( left == 0 )
  196.               break;
  197.             }
  198.         STACK_LOOP_END(ptr, size)
  199.       }
  200.     return 0;
  201. }
  202.  
  203. /* Store the top elements of a stack into an array, */
  204. /* with or without store/undo checking. */
  205. /* May return e_rangecheck or e_invalidaccess. */
  206. int
  207. ref_stack_store(const ref_stack *pstack, ref *parray, uint count, uint skip,
  208.   int age, bool check, client_name_t cname)
  209. {    uint left, pass;
  210.     ref *to;
  211.  
  212.     if ( count > ref_stack_count(pstack) || count > r_size(parray) )
  213.       return_error(e_rangecheck);
  214.     if ( check )
  215.       { int code = ref_stack_store_check(pstack, parray, count, skip);
  216.         if ( code < 0 )
  217.           return code;
  218.       }
  219.     to = parray->value.refs + count;
  220.     left = count, pass = skip;
  221.     STACK_LOOP_BEGIN(pstack, from, size)
  222.       if ( size <= pass )
  223.         pass -= size;
  224.       else
  225.         { if ( pass != 0 )
  226.         size -= pass, pass = 0;
  227.           from += size;
  228.           if ( size > left )
  229.         size = left;
  230.           left -= size;
  231.           switch ( age )
  232.         {
  233.         case -1:    /* not an array */
  234.           while ( size-- )
  235.             { from--, to--;
  236.               ref_assign(to, from);
  237.             }
  238.           break;
  239.         case 0:        /* old array */
  240.           while ( size-- )
  241.             { from--, to--;
  242.               ref_assign_old(parray, to, from, cname);
  243.             }
  244.           break;
  245.         case 1:        /* new array */
  246.           while ( size-- )
  247.             { from--, to--;
  248.               ref_assign_new(to, from);
  249.             }
  250.           break;
  251.         }
  252.           if ( left == 0 )
  253.         break;
  254.         }
  255.     STACK_LOOP_END(from, size)
  256.     r_set_size(parray, count);
  257.     return 0;
  258. }
  259.  
  260. /* Pop a given number of elements off a stack. */
  261. /* The number must not exceed the number of elements in use. */
  262. void
  263. ref_stack_pop(register ref_stack *pstack, uint count)
  264. {    uint used;
  265.     while ( (used = pstack->p + 1 - pstack->bot) < count )
  266.     {    count -= used;
  267.         pstack->p = pstack->bot - 1;
  268.         ref_stack_pop_block(pstack);
  269.     }
  270.     pstack->p -= count;
  271. }
  272.  
  273. /* Pop the top block off a stack. */
  274. int
  275. ref_stack_pop_block(register ref_stack *pstack)
  276. {    s_ptr bot = pstack->bot;
  277.     uint count = pstack->p + 1 - bot;
  278.     ref_stack_block *pcur =
  279.       (ref_stack_block *)pstack->current.value.refs;
  280.     register ref_stack_block *pnext =
  281.       (ref_stack_block *)pcur->next.value.refs;
  282.     uint used;
  283.     ref *body;
  284.     ref next;
  285.     if ( pnext == 0 )
  286.       return_error(pstack->underflow_error);
  287.     used = r_size(&pnext->used);
  288.     body = (ref *)(pnext + 1) + flat_guard(pstack->bot_guard);
  289.     next = pcur->next;
  290.     /*
  291.      * If we're on a segmented system, the top block does not move,
  292.      * so we move up the used part of the top block, copy the contents
  293.      * of the next block under it, and free the next block.
  294.      * We also do this on non-segmented systems if the contents of the
  295.      * two blocks won't fit in a single block; in this case we copy up
  296.      * as much as will fit.  On non-segmented systems where the contents
  297.      * of both blocks fit in a single block, we copy the used part
  298.      * of the top block to the top of the next block, and free
  299.      * the top block.
  300.      */
  301.     if ( used + count > pstack->body_size )
  302.       {    /* Move as much into the top block as will fit. */
  303.         uint moved = pstack->body_size - count;
  304.         uint left;
  305.         if ( moved == 0 )
  306.           return_error(e_Fatal);
  307.         memmove(bot + moved, bot, count * sizeof(ref));
  308.         left = used - moved;
  309.         memcpy(bot, body + left, moved * sizeof(ref));
  310.         refset_null(body + left, moved);
  311.         r_dec_size(&pnext->used, moved);
  312.         pstack->p = pstack->top;
  313.         pstack->extension_used -= moved;
  314.       }
  315.     else
  316.       {
  317. #if stacks_are_segmented
  318.     /* We know there are no guard elements in the next block. */
  319.     memmove(bot + used, bot, count * sizeof(ref));
  320.     memcpy(bot, body, used * sizeof(ref));
  321.     pcur->next = pnext->next;
  322.     gs_free_ref_array(pstack->memory, &next, "ref_stack_pop_block");
  323. #else
  324.     memcpy(body + used, bot, count * sizeof(ref));
  325.     pstack->bot = bot = body;
  326.     pstack->top = bot + pstack->body_size - 1;
  327.     gs_free_ref_array(pstack->memory, &pstack->current,
  328.               "ref_stack_pop_block");
  329.     pstack->current = next;
  330. #endif
  331.     pstack->p = bot + (used + count - 1);
  332.     pstack->extension_size -= pstack->body_size;
  333.     pstack->extension_used -= used;
  334.       }
  335.     return 0;
  336. }
  337.  
  338. /* Extend a stack to recover from an overflow condition. */
  339. /* May return overflow_error or e_VMerror. */
  340. int
  341. ref_stack_extend(ref_stack *pstack, uint request)
  342. {    uint keep = (pstack->top - pstack->bot + 1) / 3;
  343.     uint count = pstack->p - pstack->bot + 1;
  344.  
  345.     if ( pstack->p < pstack->bot )
  346.       {    /* Adding another block can't help things. */
  347.         return_error(pstack->overflow_error);
  348.       }
  349.     if ( keep + request > pstack->body_size )
  350.       keep = pstack->body_size - request;
  351.     if ( keep > count )
  352.       keep = count;        /* required by ref_stack_push_block */
  353.     return ref_stack_push_block(pstack, keep, request);
  354. }
  355.  
  356. /* Push N empty slots onto a stack.  These slots are not initialized; */
  357. /* the caller must fill them immediately.  May return overflow_error */
  358. /* (if max_stack would be exceeded, or the stack has no allocator) */
  359. /* or e_VMerror. */
  360. int
  361. ref_stack_push(register ref_stack *pstack, uint count)
  362. {    /* Don't bother to pre-check for overflow: we must be able to */
  363.     /* back out in the case of a VMerror anyway, and */
  364.     /* ref_stack_push_block will make the check itself. */
  365.     uint needed = count;
  366.     uint added;
  367.     for ( ; (added = pstack->top - pstack->p) < needed; needed -= added )
  368.       {    int code;
  369.         pstack->p = pstack->top;
  370.         code =
  371.           ref_stack_push_block(pstack,
  372.                        (pstack->top - pstack->bot + 1) / 3,
  373.                        count);
  374.         if ( code < 0 )
  375.           {    /* Back out. */
  376.             ref_stack_pop(pstack, count - needed);
  377.             pstack->requested = count;
  378.             return code;
  379.           }
  380.       }
  381.     pstack->p += needed;
  382.     return 0;
  383. }
  384.  
  385. /* Push a block onto the stack, specifying how many elements of */
  386. /* the current top block should remain in the top block and also */
  387. /* how many elements we are trying to add. */
  388. /* May return overflow_error or e_VMerror. */
  389. /* Must have keep <= count. */
  390. int
  391. ref_stack_push_block(register ref_stack *pstack, uint keep, uint add)
  392. {    uint count = pstack->p - pstack->bot + 1;
  393.     uint move = count - keep;
  394.     ref_stack_block *pcur = (ref_stack_block *)pstack->current.value.refs;
  395.     ref next;
  396.     ref_stack_block *pnext;
  397.     ref *body;
  398.     int code;
  399.     if ( keep > count )
  400.       return_error(e_Fatal);
  401.     /* Check for overflowing the maximum size, */
  402.     /* or expansion not allowed.  */
  403.     if ( pstack->memory == 0 ||
  404.          pstack->extension_used + (pstack->top - pstack->bot) + add >=
  405.            pstack->max_stack.value.intval ||
  406.          !pstack->allow_expansion
  407.        )
  408.       return_error(pstack->overflow_error);
  409.     code = gs_alloc_ref_array(pstack->memory, &next, 0,
  410.                   pstack->block_size, "ref_stack_push_block");
  411.     if ( code < 0 )
  412.       return code;
  413.     pnext = (ref_stack_block *)next.value.refs;
  414.     body = (ref *)(pnext + 1);
  415. #if stacks_are_segmented
  416.     /* Copy all but the top keep elements into the new block, */
  417.     /* and move the top elements down. */
  418.     /* We know there are no guard elements in the new block. */
  419.     memcpy(body, pstack->bot, move * sizeof(ref));
  420.     /* Clear the elements above the top of the new block. */
  421.     refset_null(body + move, pstack->body_size - move);
  422.     if ( keep <= move )
  423.     {    /* No overlap, memcpy is safe. */
  424.         memcpy(pstack->bot, pstack->bot + move, keep * sizeof(ref));
  425.     }
  426.     else
  427.     {    uint i;
  428.         s_ptr bot = pstack->bot;
  429.         s_ptr up = bot + move;
  430.         for ( i = 0; i < keep; i++ )
  431.             bot[i] = up[i];
  432.     }
  433.     pnext->next = pcur->next;
  434.     pnext->used = next;
  435.     pcur->next = next;
  436.     pnext->used.value.refs = body;
  437.     r_set_size(&pnext->used, move);
  438. #else
  439.     /* Copy the top keep elements into the new block, */
  440.     /* and make the new block the top block. */
  441.     init_block(pstack, &next, keep);
  442.     body += pstack->bot_guard;
  443.     memcpy(body, pstack->bot + move, keep * sizeof(ref));
  444.     /* Clear the elements above the top of the new block. */
  445.     refset_null(body + keep, pstack->body_size - keep);
  446.     /* Clear the elements above the top of the old block. */
  447.     refset_null(pstack->bot + move, keep);
  448.     pnext->next = pstack->current;
  449.     pcur->used.value.refs = pstack->bot;
  450.     r_set_size(&pcur->used, move);
  451.     pstack->current = next;
  452.     pstack->bot = body;
  453.     pstack->top = pstack->bot + pstack->body_size - 1;
  454. #endif
  455.     pstack->p = pstack->bot + keep - 1;
  456.     pstack->extension_size += pstack->body_size;
  457.     pstack->extension_used += move;
  458.     return 0;
  459. }
  460.  
  461. /* Clean up a stack for garbage collection. */
  462. void
  463. ref_stack_cleanup(ref_stack *pstack)
  464. {    ref_stack_block *pblock =
  465.       (ref_stack_block *)pstack->current.value.refs;
  466.     refset_null(pstack->p + 1, pstack->top - pstack->p);
  467.     pblock->used = pstack->current;        /* set attrs */
  468.     pblock->used.value.refs = pstack->bot;
  469.     r_set_size(&pblock->used, pstack->p + 1 - pstack->bot);
  470. }
  471.  
  472. /* ------ Internal routines ------ */
  473.  
  474. /* Initialize the guards and body of a stack block. */
  475. /* Note that this always initializes the guards, so it should not be used */
  476. /* for extension blocks in a segmented environments. */
  477. private void
  478. init_block(ref_stack *pstack, ref *psb, uint used)
  479. {    ref *brefs = psb->value.refs;
  480. #define pblock ((ref_stack_block *)brefs)
  481.     register uint i;
  482.     register ref *p;
  483.     for ( i = pstack->bot_guard, p = brefs + stack_block_refs;
  484.           i != 0; i--, p++
  485.         )
  486.         ref_assign(p, &pstack->guard_value);
  487.     /* The top guard elements will never be read, */
  488.     /* but we need to initialize them for the sake of the GC. */
  489.     /* We can use refset_null for this, because even though it uses */
  490.     /* make_null_new and stack elements must not be marked new, */
  491.     /* these slots will never actually be read or written. */
  492.     if ( pstack->top_guard )
  493.       {    ref *top = brefs + r_size(psb);
  494.         int top_guard = pstack->top_guard;
  495.         refset_null(top - top_guard, top_guard);
  496.       }
  497.     pblock->used = *psb;
  498.     pblock->used.value.refs = brefs + stack_block_refs + pstack->bot_guard;
  499.     r_set_size(&pblock->used, 0);
  500. }
  501.